import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.List;

public class Solution1 {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        return _recurrence(0,0,n,"");
    }
    //打印出所有可能的情况，排除不合理的情况
    // 左括号随便插入，但是不能超过n
    // 右括号的个数不能大于左括号的个数
    private List<String> _recurrence(int left,int right, int n, String s) {
        if(left>=n && right>=n){
            list.add(s);
            return list;
        }
        if(left<n)_recurrence(left+1,right,n,s+"(");
        if(left>0&&right<left)_recurrence(left,right+1,n,s+")");
        return list;
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        List<String> stringList = solution1.generateParenthesis(3);
        System.out.println(stringList);
    }
}

